'''
找到最左 >= target 的元素
'''
import random

def binary_search(arr, target):
    ans = -1
    l, r = 0, len(arr) - 1
    while l <= r:
        m = (l + r) // 2
        if arr[m] >= target:
            ans = m
            r = m - 1
        else:
            l = m + 1
    return ans

def comparative_search(arr, target):
    for i, num in enumerate(arr):
        if num >= target:
            return i
    return -1

def test(n, t):
    for _ in range(t):
        nums = [random.randint(-1000, 1000) for _ in range(n)]
        nums.sort()
        target = random.randint(-1000, 1000)
        res1 = binary_search(nums, target)
        res2 = comparative_search(nums, target)
        if res1 != res2:
            print("error!")
            print(f"nums: {nums}\ntarget: {target}\nres1: {res1}\nres2: {res2}")

n, t = 1000, 10000
print("测试开始!")
test(n, t)
print("测试结束!")